package LeetCode;

public class LC_390_EliminationGame {

    public static void main(String[] args) {

    }

    public class Solution {
        public int lastRemaining(int n) {
            if (n < 1) return 0;
            if (n == 1) return 1;
            int gap = 1;
            int res = 1;
            while (gap * 2 <= n) {
                res += gap;
                gap *= 2;
                if (gap * 2 <= n) {
                    if ((n / gap) % 2 == 1)
                        res += gap;
                    gap *= 2;
                }
            }
            return res;
        }

    }

    class Solution_2 {
        int lastRemaining(int n) {
            return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));
        }
    }
}
